
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>


bool isMatch(std::string s, std::string p) {
    if (p.empty())    return s.empty();
    
    if ('*' == p[1])
        return (
                isMatch(s, p.substr(2))
                || (!s.empty()
                    && (s[0] == p[0] || '.' == p[0])
                    && isMatch(s.substr(1), p))
                );
    else
        return !s.empty()
                && (s[0] == p[0] || '.' == p[0])
                && isMatch(s.substr(1), p.substr(1));
}


int main(int argc, const char * argv[])
{
    std::cout<<isMatch("ab", ".*c")<<std::endl;
    std::cout<<isMatch("aa", ".")<<std::endl;
    std::cout<<isMatch("aaa", "a")<<std::endl;
    std::cout<<isMatch("aa", "a*")<<std::endl;
    std::cout<<isMatch("aa", ".a")<<std::endl;
    std::cout<<isMatch("ab", ".*")<<std::endl;
    std::cout<<isMatch("aab", "c*a*b")<<std::endl;
    return 0;
}
